package info.xiao.dataStructrue.queue;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Classname MaxQueue
 * @Description 链接：https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof/submissions/
 * @Date 2022/10/25 15:56
 * @Created by 晓龙Oba
 */
public class MaxQueue {

    private Deque<Integer> queueA;
    private Deque<Integer> queueB;

    public MaxQueue() {
        this.queueA = new ArrayDeque<>();
        this.queueB = new ArrayDeque<>();
    }

    public int max_value() {
        return queueB.peek() == null ? -1 : queueB.peek();
    }

    public void push_back(int value) {
        queueA.offer(value);
        while (!queueB.isEmpty()) {
            Integer median = queueB.pollLast();
            if (value <= median) {
                queueB.offer(median);
                break;
            }
        }
        queueB.offer(value);
    }

    public int pop_front() {
        Integer poll = queueA.poll();
        if (poll != null && poll.equals(queueB.peek())) {
            queueB.poll();
        }
        return poll == null ? -1 : poll;
    }


    public String[] execute(String[] instruction, Integer[] variable) {

        String[] result = new String[instruction.length];
        for (int i = 0; i < instruction.length; i++) {
            if (i == 14) {
                System.out.println("");
            }
            switch (instruction[i]) {
                case "MaxQueue":
                    result[i] = "null";
                    break;
                case "max_value":
                    result[i] = this.max_value() + "";
                    break;
                case "pop_front":
                    int a = this.pop_front();
                    result[i] = "a";
                    break;
                case "push_back":
                    this.push_back(variable[i]);
                    result[i] = "null";
                    break;
            }
        }

        return result;
    }


    public static void main(String[] args) {
        MaxQueue maxQueue = new MaxQueue();
        String[] instruction =
                {"MaxQueue", "max_value", "pop_front", "max_value", "push_back", "max_value", "pop_front", "max_value", "pop_front", "push_back", "pop_front", "pop_front", "pop_front", "push_back", "pop_front", "max_value", "pop_front", "max_value", "push_back", "push_back", "max_value", "push_back", "max_value", "max_value", "max_value", "push_back", "pop_front", "max_value", "push_back", "max_value", "max_value", "max_value", "pop_front", "push_back", "push_back", "push_back", "push_back", "pop_front", "pop_front", "max_value", "pop_front", "pop_front", "max_value", "push_back", "push_back", "pop_front", "push_back", "push_back", "push_back", "push_back", "pop_front", "max_value", "push_back", "max_value", "max_value", "pop_front", "max_value", "max_value", "max_value", "push_back", "pop_front", "push_back", "pop_front", "max_value", "max_value", "max_value", "push_back", "pop_front", "push_back", "push_back", "push_back", "pop_front", "max_value", "pop_front", "max_value", "max_value", "max_value", "pop_front", "push_back", "pop_front", "push_back", "push_back", "pop_front", "push_back", "pop_front", "push_back", "pop_front", "pop_front", "push_back", "pop_front", "pop_front", "pop_front", "push_back", "push_back", "max_value", "push_back", "pop_front", "push_back", "push_back", "pop_front"};
        Integer[] variable =
                {0, 0, 0, 0, 46, 0, 0, 0, 0, 868, 0, 0, 0, 525, 0, 0, 0, 0, 123, 646, 0, 229, 0, 0, 0, 871, 0, 0, 285, 0, 0, 0, 0, 45, 140, 837, 545, 0, 0, 0, 0, 0, 0, 561, 237, 0, 633, 98, 806, 717, 0, 0, 186, 0, 0, 0, 0, 0, 0, 268, 0, 29, 0, 0, 0, 0, 866, 0, 239, 3, 850, 0, 0, 0, 0, 0, 0, 0, 310, 0, 674, 770, 0, 525, 0, 425, 0, 0, 720, 0, 0, 0, 373, 411, 0, 831, 0, 765, 701, 0};
        String[] execute = maxQueue.execute(instruction, variable);
        System.out.println(execute);
    }
}
